/*
 * Algorytm.java
 *
 * Created on 14 kwiecień 2008, 23:38
 */
package protrans;

/**
 * Algorytm Forda-Fulkersona do rozwiazania problemu transportowego 
 * Przerobiona procedura TRANSPORT z ksiazki: "Algorytmy optymalizacji dyskretnej 
 * z programami w jezyku pascal" Maciej M Syslo, Narsingh Deo, Janusz S Kowalik
 * 
 * @author Martin Suszczynski   140893
 * @author Artur Szwabowicz     140907
 * @version 1.3
 * @since 1.0
 */
public class Algorytm {

    // ko - optymalny koszt transportu
    private int ko;
    private int kroki;
    private int[] producenci;
    private int[] konsumenci;
    private int[][] koszty;
    private int[][] wynik;

    /**
     * Przyklad z wykladu:
     * prod = {15, 30, 55};
     * kons = {30, 10, 15, 45};
     * koszty = {
     *        {3, 7, 3, 4},
     *        {5, 7, 2, 6},
     *        {8, 13, 9, 4}
     *          };
     * 
     * @param prod tablica int jedno-wymiarowa producentow
     * @param kons tablica int jedno-wymiarowa konsumentow
     * @param koszt tablica int dwu-wymiarowa kosztow transportu
     * @since 1.0
     */
    public Algorytm(int[] prod, int[] kons, int[][] koszt) {
        //////////// Krok 1
        int inf = Integer.MAX_VALUE;
        producenci = prod;
        konsumenci = kons;
        koszty = koszt;
        //                 [ kolumny ]       [ wiersze ]
        wynik = new int[producenci.length][konsumenci.length];
        // zmienne dualne
        int[] u = new int[producenci.length];
        int[] v = new int[konsumenci.length];
        //------------------------------- inicjalizacja wektora v
        int r = inf;
        int i, j, ra, sf;
        // przechodzi po kolumnach
        for (int m = 0; m < producenci.length; m++) {
            // przechodzi po wierszach
            for (int n = 0; n < konsumenci.length; n++) {
                r = koszty[m][n];
            }
            v[m] = r;
        }
        // ------------------------------
        // lab(procedura A), lab2(procedura B) - warunki etykietowania
        boolean lab, lab2;
        // lab1 - warunek optymalnosci
        boolean lab1 = false;
        int[] w = new int[producenci.length];
        int[] eps = new int[producenci.length];
        int[] k = new int[konsumenci.length];
        int[] del = new int[konsumenci.length];
        //////////// Krok 2
        // sprawdzanie optymalnosci, dopoki wszystkie ograniczenia prymalnie 
        // dla kazdego m,n nie zostana spelnione
        do {
            for (int m = 0; m < producenci.length; m++) {
                w[m] = -1;
                eps[m] = producenci[m];
            }
            for (int n = 0; n < konsumenci.length; n++) {
                k[n] = -1;
                del[n] = 0;
            }
            //////////// Krok 3
            //----------------------------- etykietowanie wierszy m kolumny
            // procedura cechowania m zmiany przeplywu
            do {
                i = 0;
                lab = lab2 = true;
                do {
                    sf = eps[i];        // eps = producenci
                    eps[i] = -eps[i];
                    // wiersz I zaczyna etykietowanie
                    if (sf > 0) {
                        ra = u[i];
                        j = 0;
                        do {
                            // kolmna J moze byc etykietowana
                            if ((del[j] == 0) && (v[j] - ra == koszty[i][j])) {
                                k[j] = i;
                                del[j] = sf;
                                lab = false;
                                // osiagniecie, przelom
                                if (konsumenci[j] > 0) {
                                    lab = true;
                                    lab2 = false;
                                    sf = Math.abs(del[j]);
                                    r = konsumenci[j];
                                    if (r < sf) {
                                        sf = r;
                                    }
                                    konsumenci[j] = r - sf;
                                    do {
                                        i = k[j];
                                        wynik[i][j] += sf;
                                        j = w[i];
                                        if (j != -1) {
                                            wynik[i][j] -= sf;
                                        }
                                    } while (j != -1);
                                    producenci[i] -= sf;

                                    // jesli konsumenci[n] <= 0 dla wszystkich n, 
                                    // to mamy OPTIMAL
                                    j = 0;
                                    do {
                                        lab1 = (konsumenci[j] <= 0);
                                        j++;
                                    } while ((j < konsumenci.length) && (lab1));
                                    if (lab1) {
                                        ko = 0;
                                        for (int m = 0; m < producenci.length; m++) {
                                            for (int n = 0; n < konsumenci.length; n++) {
                                                ko += wynik[m][n] * koszty[m][n];
                                            }
                                        }
                                    }
                                }
                            }
                            j++;
                        } while ((j < konsumenci.length) && (lab2));
                    }
                    i++;
                } while ((i < producenci.length) && (lab2));
                // etykietowanie wierszy z kolumn
                if (!lab) {
                    lab = true;
                    for (int n = 0; n < konsumenci.length; n++) {
                        sf = del[n];
                        if (sf > 0) {
                            for (int m = 0; m < producenci.length; m++) {
                                if (eps[m] == 0) {
                                    r = wynik[m][n];
                                    if (r > 0) {
                                        w[m] = n;
                                        if (r <= sf) {
                                            eps[m] = r;
                                        } else {
                                            eps[m] = sf;
                                        }
                                        lab = false;
                                    }
                                }
                            }
                            del[n] = -sf;
                        }
                    }
                }
            } while (!lab);
            //------------------------------------- koniec etykietowania
            //////////// Krok 4
            // modyfikacja zmiennych dualnych
            if (lab2) {
                // r - przyrost delta
                r = inf;
                // szukanie najmniejszego r
                for (int m = 0; m < producenci.length; m++) {
                    if (eps[m] != 0) {
                        ra = u[m];
                        for (int n = 0; n < konsumenci.length; n++) {
                            if (del[n] == 0) {
                                sf = koszty[m][n] + ra - v[n];
                                if (r > sf) {
                                    r = sf;
                                }
                            }
                        }
                    }
                }
                // generowanie wektora u
                for (int m = 0; m < producenci.length; m++) {
                    if (eps[m] == 0) {
                        u[m] += r;
                    }
                }
                // generowanie wektora v
                for (int n = 0; n < konsumenci.length; n++) {
                    if (del[n] == 0) {
                        v[n] += r;
                    }
                }
            }
            kroki++;
            if (kroki == 10000) {
                javax.swing.JOptionPane.showMessageDialog(null, "Brak wyniku\nAlgorytm wszedl w petle nieskonczona");
                lab1 = true;
                wynik = koszty;
            }
        } while (!lab1);    // warunek optymalnosci
    }

    /**
     * Przyklad z wykladu: wynik = {
     *        {15, 0, 0, 0},
     *        {5, 10, 15, 0},
     *        {10, 0, 0, 45}
     *          };
     * 
     * @return sWynik - String z zawartoscia tablicy wynik
     * @since 1.0
     */
    public String getWynik() {
        String sWynik = new String();
        Integer xx = new Integer(0);
        for (int p = 0; p < producenci.length; p++) {
            for (int k = 0; k < konsumenci.length; k++) {
                xx = wynik[p][k];
                sWynik += Integer.toString(xx) + " ";
            }
            sWynik += "\n";
        }
        return sWynik;
    }
    /**
     * 
     * @return ko - int optymalny koszt przewozu
     * @since 1.2
     */
    public int getKo() {
        return ko;
    }
    
    /**
     * 
     * @return ko - String optymalny koszt przewozu
     * @since 1.2
     */
    public String getStringKo() {
        String out = Integer.toString(ko);
        return out;
    }
}
